package 左哥算法.ch12滑动窗口与双端队列;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class T {
    @Test
    public void test(){
        int[] arr={0,4,3,0};
        int x=0;
        System.out.println(Arrays.toString(twoSum(arr, x)));
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer,int[]> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i],i);
            int[] ints = map.get(nums[i]);
            if (ints!=null) {
                ints[1]=i;
            }else {
                map.put(nums[i],new int[]{i,0});
            }
        }
        Arrays.sort(nums);
        int r = find(nums, target);
        int l=0;
        while(l<r){
            if (nums[l]+nums[r]==target) {
                if (nums[l]==nums[r]){
                    return new int[]{map.get(nums[l])[0],map.get(nums[l])[1]};
                }
                return new int[]{map.get(nums[l])[0], map.get(nums[r])[0]};
            }
            if (nums[l]+nums[r]>target) {
                r--;
            }else {
                l++;
            }
        }
        return null;
    }
    public int find(int[] nums,int t){
        int l=0,r=nums.length-1;
        while (l<=r){
            int mid=l+r>>1;
            if (nums[mid]<=t){
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
        return r;
    }
}
